package leetcode.premium

import kotlinetc.println
import leetcode.groupAnagrams

/**
Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd".
We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]

similar [groupAnagrams]
 */
fun main(args: Array<String>) {

//    groupShiftStrings(arrayOf("abc", "bcd", "acef", "xyz", "az", "ba", "a", "z")).println()

//    isPrime(4).println()


//    isPrime(107).println()
//    gapPrimes(2, 100, 110).asList().println()
    Int.MAX_VALUE.println()
    Math.sqrt(2147395600.toDouble()).toInt().println()
    mySqrt(2147395600).println()
}


//codewars


fun mySqrt(x: Int): Int {

    var root = 1


    //overflow check
    while (root * root in 1..x) root++
    return --root
}


fun gapPrimes(g: Int, m: Long, n: Long): LongArray {

    var i = m



    while (i <= n) {
        if (isPrime(i) && isPrime(i + g)) {
            var midPrim = false
            for (j in i + 1 until i + g)
                if (isPrime(j)) {
                    i = j
                    midPrim = true
                    break
                }
            if (midPrim.not())
                return longArrayOf(i, i + g)

        } else i++
    }
    return longArrayOf()

}


fun isPrime(number: Long): Boolean {

    var i = 2
    while (i * i <= number) {
        if (number % i == 0L)
            return false
        i++
    }
    return true
}


fun groupShiftStrings(strs: Array<String>): List<List<String>> {

    val map = hashMapOf<String, ArrayList<String>>()

    strs.forEach {
        val profile = profileShiftString(it)
        if (map.containsKey(profile)) {
            map[profile]!!.add(it)
        } else {
            val list = ArrayList<String>()
            list.add(it)
            map[profile] = list
        }
    }
    return map.values.toList()
}

/**
 *
 */
fun profileShiftString(str: String): String {
    val profile = StringBuffer()

    profile.append(str.length)
    var i = 0
    while (i < str.length - 1) {
        var v = str[i + 1] - str[i]
        if (v < 0) {
            v = (v + 26) % 26
        }
        profile.append(v)
        i++
    }

    return profile.toString()
}



